package leetcode.code1361;

public class Solution2 {

	class Union {

		private int n;
		private int[] parent;
		private int[] sizes;
		private int[] stack;

		public Union(int n) {
			this.n = n;
			this.parent = new int[n];
			this.sizes = new int[n];
			this.stack = new int[n];
			for (int i = 0; i < n; i++) {
				parent[i] = i;
				sizes[i] = 1;
			}
		}

		public int findParent(int num) {
			int root = this.parent[num];
			int p = -1;
			while (root != num) {
				this.stack[++p] = num;
				num = root;
				root = this.parent[num];
			}
			while (p > -1) {
				num = stack[p--];
				this.parent[num] = root;
			}
			return root;
		}

		public boolean isSameSet(int num1, int num2) {
			return this.findParent(num1) == this.findParent(num2);
		}

		public void union(int num1, int num2) {
			int p1 = this.findParent(num1);
			int p2 = this.findParent(num2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.parent[p1] = p2;
					this.sizes[p2] += size1;
				} else {
					this.parent[p2] = p1;
					this.sizes[p1] += size2;
				}
			}
		}

	}

	public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
